package demo.lintcode;

import java.util.Arrays;

public class P92 {
    public static void main(String[] args) {
        P92 p92 = new P92();
        p92.backPack(10, new int[]{20,15,15,15,15,15,15,15,15,15,15,15,15,15,15,7,2,15,15,15,15});
    }

    public int backPack(int m, int[] A) {
        // write your code here
        boolean dp[] = new boolean[m + 1];
        Arrays.sort(A);
        dp[0] = true;

        int sum = 0;
        for (int i = 0; i < A.length; i++) {
            for (int j = 1; j <= sum && j + A[i] <= m; j++) {
                if (dp[j] && j + A[i] <= m)
                    dp[j + A[i]] = true;
                // dp[j + A[i]] = dp[j + A[i]]|| dp[j] && j + A[i] <= m;
            }
            if(A[i]<=m)
            dp[A[i]]=true;
            sum += A[i];
        }

        for (int k = m; k >= 0; k--) {
            if (dp[k])
                return k;
        }
        return 0;
    }
}
